首页 > 试题广场 >

附加题

[编程题]附加题

热度指数：29760 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

存在n+1个房间，每个房间依次为房间1 2 3...i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略：
A. 如果访问过当前房间 i 偶数次，那么下一次移动到房间i+1；
B. 如果访问过当前房间 i 奇数次，那么移动到房间pi；
现在路人甲想知道移动到房间n+1一共需要多少次移动；

输入描述:

第一行包括一个数字n(30%数据1<=n<=100，100%数据 1<=n<=1000)，表示房间的数量，接下来一行存在n个数字 pi(1<=pi<=i), pi表示从房间i可以传送到房间pi。

输出描述:

输出一行数字，表示最终移动的次数，最终结果需要对1000000007 (10e9 + 7) 取模。

示例1

输入

2
1 2

输出

说明

开始从房间1 只访问一次所以只能跳到p1即 房间1， 之后采用策略A跳到房间2，房间2这时访问了一次因此采用策略B跳到房间2，之后采用策略A跳到房间3，因此到达房间3需要 4 步操作。

算法知识视频讲解

Python 3

牛客665150653号

n=int(input())
pi=list(map(int,input().split()))
dp=[0 for i in range(n+1)]
for i in range(1,n+1):
    #dp[i]第一次到i所需的移动次数，此处的i就是n+1
    dp[i]=(dp[i-1]+(dp[i-1]+1-dp[pi[i-1]-1])+1)%1000000007
print(dp[-1])

发表于 2022-06-24 10:19:31 回复(0)

Python 3

xinghudamowang

# 设dp[i] = 两次到达第i房间。
# 则dp[i] = 第一次到达i + 第二次到达i
# 设dd[i] = 第二次到达i
# 有dp[i] = dp[i-1]+1 + dd(i)+1
# 因为第一次到达i 后，会跳到pi
# 又因为pi<=i 所以第二次到达i时，i-1也必须到达偶数次。
# 因此dd[i] = 跳到pi后回到 i-1 点次数 +1
# 因为跳到pi 点时，pi进入奇数次
# 所以从pi 点到达i-1 点且i-1次数为偶数的次数，等价于从pi-1点到i-1点且i-1点为偶数次数-1，即dp[i-1]-dp[pi-1]-1
# 因此 dd[i] = dp[i-1] - dp[pi-1]
# 即 dp[i] = 2*dp[i-1]-dp[pi[i]-1] +2

n=int(input())
pi = list(map(int,input().split(' ')))
def solution(n,pi):
dp = [0]*(1+n)
pi.insert(0,0)
mod = 1000000007
for i in range(1,n+1):
dp[i] = 2*dp[i-1]-dp[pi[i]-1] +2
# print(dp[i],dp[i-1],dp[pi[i]-1])
print(dp[n] % mod)



solution(n, pi)

发表于 2022-06-12 01:08:44 回复(0)